
class union_set:

    def __init__(self, n: int):
        self.parent = [i for i in range(n)]
        self.size = [1 for _ in range(n)]
        self.help = [0] * n
        self.sets = n

    # 找根
    def __find_head(self, i: int) -> int:
        help_idx = 0
        while i != self.parent[i]:      # 找根, 同时 利用help记录寻找过程,将过程的节点们都直接指向根
            self.help[help_idx] = i
            i = self.parent[i]
            help_idx += 1
        while help_idx > 0:     # 一路记录的都直接指向 根
            help_idx -= 1
            self.parent[self.help[help_idx]] = i
        return i

    # 是否同一个集
    def is_sameset(self, a: int, b: int) -> bool:
        return self.__find_head(a) == self.__find_head(b)

    # 合并
    def union(self, i: int, j: int) -> None:
        headi, headj = self.__find_head(i), self.__find_head(j)
        if headi != headj:
            if self.size[headi] >= self.size[headj]:
                self.parent[headj] = headi
                self.size[headi] += self.size[headj]
                self.size[headj] = 0
            else:
                self.parent[headi] = headj
                self.size[headj] += self.size[headi]
                self.size[headi] = 0
            self.sets -= 1
        return

    # 现在有多少个集
    def sets(self) -> None:
        return self.sets

